Private set intersection (PSI) allows two parties to find the intersection of their sets without revealing the data elements of their sets to each other. PSI has numerous real-world applications including privacy-preserving data mining, location-based services and genomic computations. More specifically, a PSI protocol allows two parties P1 and P2 to find the intersection of two sets S1 and S2 from some universe U without having to disclose the sets to each other. In other words, with a PSI protocol P1 and P2 can find the intersection I=S1∩S2 of their sets without learning any information about the other party's set beyond its size.
With a server-aided PSI protocol, the two parties P1 and P2 can, in addition, outsource some of their computations to an untrusted server—instantiated, for example, in the cloud. Server-aided PSI protocols are more efficient for clients than traditional PSI protocols by several orders of magnitude.